package leetcode.editor.cn.dsa14_greedyAlgorithm;
//在一排多米诺骨牌中，A[i] 和 B[i] 分别代表第 i 个多米诺骨牌的上半部分和下半部分。（一个多米诺是两个从 1 到 6 的数字同列平铺形成的 ——
//该平铺的每一半上都有一个数字。） 
//
// 我们可以旋转第 i 张多米诺，使得 A[i] 和 B[i] 的值交换。 
// 返回能使 A 中所有值或者 B 中所有值都相同的最小旋转次数。
// 如果无法做到，返回 -1.
//
// 示例 1： 
// 输入：A = [2,1,2,4,2,2], B = [5,2,6,2,3,2]
// 输出：2
// 解释：
// 图一表示：在我们旋转之前， A 和 B 给出的多米诺牌。
// 如果我们旋转第二个和第四个多米诺骨牌，我们可以使上面一行中的每个值都等于 2，如图二所示。
// 
// 示例 2：
// 输入：A = [3,5,1,2,3], B = [3,6,3,3,4]
// 输出：-1
// 解释：
// 在这种情况下，不可能旋转多米诺牌使一行的值相等。
//
// 提示：
// 1 <= A[i], B[i] <= 6
// 2 <= A.length == B.length <= 20000 
// 
// Related Topics 贪心算法 数组 
// 👍 55 👎 0

public class MinimumDominoRotationsForEqualRow1007 {
    public static void main(String[] args) {
        Solution solution = new MinimumDominoRotationsForEqualRow1007().new Solution();
        int[] arr1 = {2,1,2,4,2,2}, arr2 = {5,2,6,2,3,2};
        System.out.println(solution.minDominoRotations(arr1, arr2)); //2
        int[] arr3 = {3,5,1,2,3}, arr4 = {3,6,3,3,4};
        System.out.println(solution.minDominoRotations(arr3, arr4)); //-1
        int[] arr5 = {1,1,1,1}, arr6 = {1,2,6,1};
        System.out.println(solution.minDominoRotations(arr5, arr6)); //0
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int minDominoRotations(int[] A, int[] B) {
            int n = A.length;
            // 使用数组模拟哈希表，记录 1-6 数字出现的次数
            int[] countA = new int[6]; // 统计在A中出现的次数
            int[] countB = new int[6]; // 统计在B中出现的次数
            int[] countAB = new int[6]; // 统计在骨牌出现的次数
            for (int i = 0; i < n; i++) {
                countA[A[i] - 1]++;
                countB[B[i] - 1]++;
                countAB[A[i] - 1]++;
                // 骨牌上下部分都出现只记为一次
                if (B[i] != A[i]) {
                    countAB[B[i] - 1]++;
                }
            }
            // 在骨牌统计表找到出现次数等于骨牌总数的数字
            for (int i = 0; i < 6; i++) {
                if (countAB[i] == n) {
                    // 计算最小的旋转次数
                    return n - Math.max(countA[i], countB[i]);
                }
            }
            return -1; // 找不到返回-1
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)
}